﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace dijiesi
{
    class dijiesi
    {
        List<List<int>> points_adj_new = new List<List<int>>();//防止路径往回跑
        List<List<int>> paths = new List<List<int>>();//存储计算出来的临时路径，并进行实时更新
        List<int> paths_dis = new List<int>();//临时路径对应的距离

        public void Dijkstra()
        {
            //1、原始数据
            int[] points_Index = new int[20] { p0, p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11, p12, p13, p14, p15, p16, p17, p18, p19 };//点序列号
            int[,] points_Matrix = new int[20, 20] { { 0,3000,0,0,1500,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{ 3000,0,3000,0,0,1500,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
            { 0,3000,0,3000,0,0,1500,0,0,0,0,0,0,0,0,0,0,0,0,0},{ 0,0,3000,0,0,0,0,1500,0,0,0,0,0,0,0,0,0,0,0,0},

            { 1500,0,0,0,0,3000,0,0,1500,0,0,0,0,0,0,0,0,0,0,0},{ 0,1500,0,0,3000,0,3000,0,0,1500,0,0,0,0,0,0,0,0,0,0},{ 0,0,1500,0,0,3000,0,3000,0,0,1500,0,0,0,0,0,0,0,0,0},{ 0,0,0,1500,0,0,3000,0,0,0,0,1500,0,0,0,0,0,0,0,0},

            { 0,0,0,0,1500,0,0,0,0,3000,0,0,1500,0,0,0,0,0,0,0},{ 0,0,0,0,0,1500,0,0,3000,0,3000,0,0,1500,0,0,0,0,0,0},{ 0,0,0,0,0,0,1500,0,0,3000,0,3000,0,0,0,0,0,0,0,0},{ 0,0,0,0,0,0,0,1500,0,0,3000,0,0,0,0,0,0,0,0,0},

            { 0,0,0,0,0,0,0,0,1500,0,0,0,0,3000,0,0,1500,0,0,0},{ 0,0,0,0,0,0,0,0,0,1500,0,0,3000,0,3000,0,0,1500,0,0},{ 0,0,0,0,0,0,0,0,0,0,1500,0,0,3000,0,3000,0,0,1500,0},{ 0,0,0,0,0,0,0,0,0,0,0,1500,0,0,3000,0,0,0,0,1500},

            { 0,0,0,0,0,0,0,0,0,0,0,0,1500,0,0,0,0,3000,0,0},{ 0,0,0,0,0,0,0,0,0,0,0,0,0,1500,0,0,3000,0,3000,0},
            { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,1500,0,0,3000,0,3000},{ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1500,0,0,3000,0}};//点与点之间的矩阵，矩阵数据为0或者距离值
            List<List<int>> points_adj_orign = new List<List<int>>();//点与点之间的临接矩阵
            for (int i = 0; i < points_Matrix.GetLength(0); i++)
            {
                List<int> point_adj = new List<int>();
                for (int j = 0; j < points_Matrix.GetLength(0); j++)
                {
                    if (points_Matrix[i, j] != 0)
                    {
                        point_adj.Add(j);
                    }
                }
                points_adj_orign.Add(point_adj);
            }
            int point_s = p1, point_e = p3;//路径起始点，路径最终点
            //2、定义参数

            Boolean is_not_Find = true;//最短路径是否找到
            //3、定义临时参数
            List<int> current_path = new List<int>();//当前路径
            int current_point;//当前点
            int next_point;//下一个点
            int current_path_Dis;//当前路径距离

            //路径初始化，先有开始点开始
            current_path.Add(point_s);
            current_path_Dis = 0;
            paths.Add(current_path);
            paths_dis.Add(0);
            current_point = point_s;

            for (int i = 0; i < points_adj_orign.Count; i++)
            {
                List<int> point_adj = new List<int>();
                for (int j = 0; j < points_adj_orign[i].Count; j++)
                {
                    point_adj.Add(points_adj_orign[i][j]);
                }
                points_adj_new.Add(point_adj);
            }

            //4、开始进行计算
            while (is_not_Find)//如果最短路径没有找到，则进行计算
            {
                ReturnMinDisPath(out current_path, out current_path_Dis);
                current_point = current_path[current_path.Count - 1];
                //判断当前最短路径的最后一个点是终点，则计算结束
                if (current_point == point_e)
                {
                    is_not_Find = false;
                }
                else//判断当前最短路径的最后一个点不是终点，则继续寻找下一个点
                {
                    //1、如果当前点是断点，则返回到while语句，继续寻找下一条最短路径
                    if (points_adj_new[current_point].Count == 0)
                    {
                        //不进行任何执行
                    }
                    else
                    {
                        //4.1、由当前点根据临接矩阵寻找相邻的其他点，并进行路径节点添加
                        for (int i = 0; i < points_adj_new[current_point].Count; i++)
                        {
                            //判断存在相邻点，如果不存在相邻点
                            next_point = points_adj_new[current_point][i];
                            //如果存在，则需要进行判断，保留路径最短的线；
                            List<int> new_one_path = new List<int>();
                            for (int k = 0; k < current_path.Count; k++)
                            {
                                new_one_path.Add(current_path[k]);
                            }
                            //添加新的一条路径，并记录长度
                            new_one_path.Add(next_point);
                            int new_path_dis = current_path_Dis + points_Matrix[current_point, next_point];
                            //将新路径添加到可能路径池中
                            AddNewPath(new_one_path, new_path_dis);
                            //修改临接矩阵节点
                            points_adj_new[next_point].Remove(current_point);
                        }
                    }
                }
            }

            //路径输出
            string path = null;
            for (int i = 0; i < current_path.Count; i++)
            {
                path = path + current_path[i] + ":";
            }
            path = path + "=" + current_path_Dis;
            MessageBox.Show(path);

        }

        /// <summary>
        /// 从可能的路径中返回一条，路径最短的一条路及对应的路径值，然后进行计算
        /// 通过每条路线路径进行判定
        /// 同时删除可能路径中的最短路径，及对应的值，进行更新
        /// </summary>
        /// <returns></returns>
        private void ReturnMinDisPath(out List<int> min_Path, out int min_Dis)
        {
            min_Dis = paths_dis[0];
            int min_Index = 0;

            for (int i = 1; i < paths_dis.Count; i++)
            {
                if (paths_dis[i]< min_Dis)
                {
                    min_Dis = paths_dis[i];
                    min_Index = i;
                }
            }
            min_Path = paths[min_Index];

            paths.RemoveAt(min_Index);
            paths_dis.RemoveAt(min_Index);
        }

        /// <summary>
        /// 将新路径添加到可能路径池中,如果资源池路线中，路线最后一个节点一样，表示存在多条路线
        /// 需要进行判断，保留路径最短的路线，删除路径长的路线，并对应的修改相关数值
        /// </summary>
        private void AddNewPath(List<int> new_one_path, int new_dis)
        {
            Boolean isSamePoint = false;
            for (int i = 0; i < paths.Count; i++)
            {
                if (paths[i][paths[i].Count - 1] == new_one_path[new_one_path.Count - 1])
                {
                    isSamePoint = true;
                    //如果新资源池中数据比新路径大，则需要更换路径
                    if (paths_dis[i] > new_dis)
                    {
                        //旧路径删除
                        paths.RemoveAt(i);
                        paths_dis.RemoveAt(i);
                        //新路径添加
                        paths.Add(new_one_path);
                        paths_dis.Add(new_dis);
                    }
                    else
                    {
                        //如果，新路径比资源池中距离大，则不执行
                    }
                }
            }
            if (isSamePoint==false)
            {
                paths.Add(new_one_path);
                paths_dis.Add(new_dis);
            }
        }

    }
}
